//给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。 
//
// 示例 1: 
//
// 输入:
//[
// [ 1, 2, 3 ],
// [ 4, 5, 6 ],
// [ 7, 8, 9 ]
//]
//输出: [1,2,3,6,9,8,7,4,5]
// 
//
// 示例 2: 
//
// 输入:
//[
//  [1, 2, 3, 4],
//  [5, 6, 7, 8],
//  [9,10,11,12]
//]
//输出: [1,2,3,4,8,12,11,10,9,5,6,7]
// 
// Related Topics 数组 
// 👍 557 👎 0

package leetcode.editor.cn;

import common.util.MyUtil;

import java.util.ArrayList;
import java.util.List;

/**
 * Java：螺旋矩阵
 *
 * @author changgui
 */
@SuppressWarnings("all")
public class P54_SpiralMatrix {
    public static void main(String[] args) {
        Solution solution = new P54_SpiralMatrix().new Solution();
        int[][] matrix = {
                {1}, {2}, {3}, {4}, {5}, {6}, {7}, {8}, {9}, {10}
        };
        MyUtil.print(solution.spiralOrder(matrix));

    }

    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * 对角线做起始点开始遍历，记录是否已遍历
     */
    class Solution {
        public List<Integer> spiralOrder(int[][] matrix) {
            List<Integer> list = new ArrayList<>();
            if (matrix == null || matrix.length == 0) {
                return list;
            }
            // 访问记录
            boolean[][] matrixAccess = new boolean[matrix.length][matrix[0].length];
            for (int i = 0; i < (matrix.length + 1) / 2; i++) {
                // 右边界纵坐标
                int ry = matrix[i].length - i - 1;
                // 下边界横坐标
                int dx = matrix.length - i - 1;
                // 左边界纵坐标
                int ly = i;
                // 上边界横坐标
                int tx = i + 1;

                // 左 -> 右
                for (int j = i; dx >= 0 && j <= ry; j++) {
                    if (!matrixAccess[i][j]) {
                        list.add(matrix[i][j]);
                        matrixAccess[i][j] = true;
                    }
                }
                // 上 -> 下
                for (int j = i + 1; ry >= 0 && j <= dx; j++) {
                    if (!matrixAccess[j][ry]) {
                        list.add(matrix[j][ry]);
                        matrixAccess[j][ry] = true;
                    }
                }
                // 右 -> 左
                for (int j = ry - 1; dx >= 0 && j >= ly; j--) {
                    if (!matrixAccess[dx][j]) {
                        list.add(matrix[dx][j]);
                        matrixAccess[dx][j] = true;
                    }
                }
                // 下 -> 上
                for (int j = dx - 1; ly < matrix[0].length && j >= tx; j--) {
                    if (!matrixAccess[j][ly]) {
                        list.add(matrix[j][ly]);
                        matrixAccess[j][ly] = true;
                    }
                }
            }
            return list;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}